﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _39_CombinationSum
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] c = new int[] { 2, 3, 6, 7 };
            int r = 7;

            IList<IList<int>> result = CombinationSum(c, r);

            Console.WriteLine();

        }

        private static IList<IList<int>> CombinationSum(int[] candidates, int target)
        {
            candidates = candidates.ToList().OrderBy(s=>s).ToArray();
            List<List<int>> result = new List<List<int>>();
            getResult(result, new List<int>(), candidates, target, 0);

            return result as IList<IList<int>>;
        }

        private static void getResult(List<List<int>> result, List<int> cur, int[] candidates, int target, int start)
        {
            if (target > 0)
            {
                for (int i = start; i < candidates.Length && target >= candidates[i]; i++)
                {
                    cur.Add(candidates[i]);
                    getResult(result, cur, candidates, target - candidates[i], i);
                    cur.Remove(cur.Count() - 1);
                }//for
            }//if
            else if (target == 0)
            {
                result.Add(new List<int>(cur));
            }//else if
        }
    }
}
